package com.learn.tree;

/**
 * 判断一棵树是否为平衡二叉树
 */
public class BalanceTree {
    public static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class Info {
        private boolean isBalance;
        private int height;

        public Info(int height, boolean isBalance) {
            this.height = height;
            this.isBalance = isBalance;
        }
    }


    public boolean isBalanceTree(Node node) {
        return process(node).isBalance;
    }

    public Info process(Node node) {
        if (node == null) {
            return new Info(0, true);
        }

        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isBalance = true;
        if (!leftInfo.isBalance || !rightInfo.isBalance || Math.abs(rightInfo.height - leftInfo.height) > 1) {
            isBalance = false;
        }
        return new Info(height, isBalance);
    }
}
